Thực đơn
NL (độ phức tạp) Quan hệ với các lớp khácNL nằm trong P do có thuật toán đa thức cho bài toán liên thông có hướng ST, nhưng vẫn chưa biết liệu NL có bằng P và liệu L có bằng NL. Năm 1987, Neil Immerman và Róbert Szelepcsényi đã độc lập chứng minh NL=co-NL (định lý Immerman-Szelepcsényi) và đã được nhận giải Gödel năm 1995 cho công trình này.[1][2]
Thực đơn
NL (độ phức tạp) Quan hệ với các lớp khácLiên quan
NLE Choppa NL (độ phức tạp) NLP NLTT 39886 Nla.gov.au NLTK NLG NLUI NLH .nlTài liệu tham khảo
WikiPedia: NL (độ phức tạp) http://www.cs.umass.edu/~immerman/pub/space.ps http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l7.ps //doi.org/10.1007%2FBF00299636 https://archive.org/details/introductiontoth00sips https://archive.org/details/introductiontoth00sips...